﻿#include <iostream>

#define MIN(a, b) (a < b ? a : b)
#define BIG_NUMBER 0x1fffffff

static int recur(const int* coins, const size_t coinCount, int index, int remain)
{
	if (remain == 0) return 0;

	if (remain < 0) return BIG_NUMBER;

	if (index >= coinCount) return BIG_NUMBER;

	int used = BIG_NUMBER;
	for (int curCount = 0; remain - coins[index] * curCount >= 0; curCount++)
	{
		used = MIN(used, curCount + recur(coins, coinCount, index + 1, remain - coins[index] * curCount));
	}

	return used;
}

static int byStrictTable(const int* coins, const size_t coinCount, int target)
{
	int remainSize = target + 1;
	int indexSize = coinCount;
	int* dp = (int*)malloc(remainSize * indexSize * sizeof(int));
	memset(dp, 0, remainSize * indexSize * sizeof(int));

	// dp(index, remain) = dp(index + remain * indexSize)
	for (int remain = 1; remain <= target; remain++)
	{
		for (int index = coinCount - 1; index >= 0; index--)
		{
			int used = BIG_NUMBER;
			for (int curCount = 0; remain - coins[index] * curCount >= 0; curCount++)
			{
				int after = BIG_NUMBER;
				if (index + 1 < coinCount)
				{
					after = dp[index + 1 + (remain - coins[index] * curCount) * indexSize];
				}

				used = MIN(used, curCount + after);
			}

			dp[index + remain * indexSize] = used;
		}
	}

	int res = dp[target * indexSize];
	free(dp);
	return res;
}

// 去掉byStrictTable中的第三重for循环
static int byStrictTable_discard3rdFor(const int* coins, const size_t coinCount, int target)
{
	int remainSize = target + 1;
	int indexSize = coinCount;
	int* dp = (int*)malloc(remainSize * indexSize * sizeof(int));
	memset(dp, 0, remainSize * indexSize * sizeof(int));

	// dp(index, remain) = dp(index + remain * indexSize)
	for (int remain = 1; remain <= target; remain++)
	{
		for (int index = coinCount - 1; index >= 0; index--)
		{
			// dp(index, remain - coins[index]) = 
			// for (int curCount = 0; remain - coins[index] - coins[index] * curCount >= 0; curCount++)
			// {
			//    after = dp[index + 1 + (remain - coins[index] - coins[index] * curCount) * indexSize];
			// }

			int used = remain - coins[index] >= 0 ? 1 + dp[index + (remain - coins[index]) * indexSize] : BIG_NUMBER;
			int used0 = index + 1 < coinCount ? dp[index + 1 + remain * indexSize] : BIG_NUMBER;
			used = MIN(used, used0);

			dp[index + remain * indexSize] = used;
		}
	}

	int res = dp[target * indexSize];
	free(dp);
	return res;
}

// 有一组各个面值的硬币，可能有重复的值，每个面值的硬币可以使用多枚，凑出指定的值最少用多少枚硬币？
// 比如：用[2, 7, 3, 5, 3] 凑出10.
int main_EmitSpecifiedCoinValue()
{
	int coins[] = { 2,7,3,5,3 };
	int coinCount = sizeof(coins) / sizeof(int);
	int target = 50;
	int atLeastUsed = recur(coins, coinCount, 0, target);
	int byStrictTableValue = byStrictTable(coins, coinCount, target);
	int byStrictTableValue_discard3rdFor = byStrictTable_discard3rdFor(coins, coinCount, target);
	printf("%d,%d,%d\n", atLeastUsed, byStrictTableValue, byStrictTableValue_discard3rdFor);

	return 0;
}